//
// Created by francklinson on 2021/7/11 AT 21:44.
//
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Solution {
private:
    vector<pair<int, int>> movement{{1,  0},
                                    {-1, 0},
                                    {0,  1},
                                    {0,  -1}};
public:
    int numEnclaves(vector<vector<int>> &grid) {
        /**
         * 从矩阵边缘的陆地进行搜索，将联通的陆地都设置为海
         * 再遍历一次 剩下的都是飞地的面积
         */
        unsigned int m = grid.size(), n = grid[0].size();
        for (int j = 0; j < n; ++j) {
            // 第一行
            if (grid[0][j] == 1) BFS(grid, 0, j);
            // 最后一行
            if (grid[m - 1][j] == 1) BFS(grid, m - 1, j);
        }
        for (int i = 0; i < m; ++i) {
            // 第一列
            if (grid[i][0] == 1) BFS(grid, i, 0);
            // 最后一列
            if (grid[i][n - 1] == 1) BFS(grid, i, n - 1);
        }
        int counter = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) ++counter;
            }
        }
        return counter;
    }

    /**
     * 执行BFS搜索联通的陆地
     * @param grid
     * @param i
     * @param j
     */
    void BFS(vector<vector<int>> &grid, int i, int j) {
        queue<pair<int, int>> q;
        q.emplace(i, j);
        grid[i][j] = 0;
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            for (int k = 0; k < 4; ++k) {
                int nextI = p.first + movement[k].first;
                int nextJ = p.second + movement[k].second;
                if (nextI >= 0 and nextI < grid.size() and nextJ >= 0 and nextJ < grid[0].size() and
                    grid[nextI][nextJ] == 1) {
                    q.emplace(nextI, nextJ);
                    grid[nextI][nextJ] = 0;
                }
            }
        }
    }
};

int main() {
    vector<vector<int>> grid{{0, 0, 0, 0},
                             {1, 0, 1, 0},
                             {0, 1, 1, 0},
                             {0, 0, 0, 0}};
    Solution sol;
    cout << sol.numEnclaves(grid) << endl;
    return 0;
}

